{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Building Where Alice and Bob Can Meet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #binary-indexed-tree #segment-tree #array #binary-search #monotonic-stack #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树状数组 #线段树 #数组 #二分查找 #单调栈 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: leftmostBuildingQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到 Alice 和 Bob 可以相遇的建筑"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的正整数数组&nbsp;<code>heights</code>&nbsp;，其中&nbsp;<code>heights[i]</code>&nbsp;表示第 <code>i</code>&nbsp;栋建筑的高度。</p>\n",
    "\n",
    "<p>如果一个人在建筑&nbsp;<code>i</code>&nbsp;，且存在&nbsp;<code>i &lt; j</code>&nbsp;的建筑&nbsp;<code>j</code>&nbsp;满足&nbsp;<code>heights[i] &lt; heights[j]</code>&nbsp;，那么这个人可以移动到建筑&nbsp;<code>j</code>&nbsp;。</p>\n",
    "\n",
    "<p>给你另外一个数组&nbsp;<code>queries</code>&nbsp;，其中&nbsp;<code>queries[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;。第&nbsp;<code>i</code>&nbsp;个查询中，Alice 在建筑&nbsp;<code>a<sub>i</sub></code> ，Bob 在建筑&nbsp;<code>b<sub>i</sub></code><sub>&nbsp;</sub>。</p>\n",
    "\n",
    "<p>请你能返回一个数组&nbsp;<code>ans</code>&nbsp;，其中&nbsp;<code>ans[i]</code>&nbsp;是第&nbsp;<code>i</code>&nbsp;个查询中，Alice 和 Bob 可以相遇的&nbsp;<strong>最左边的建筑</strong>&nbsp;。如果对于查询&nbsp;<code>i</code>&nbsp;，Alice<em> </em>和<em> </em>Bob 不能相遇，令&nbsp;<code>ans[i]</code> 为&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>heights = [6,4,8,5,2,7], queries = [[0,1],[0,3],[2,4],[3,4],[2,2]]\n",
    "<b>输出：</b>[2,5,-1,5,2]\n",
    "<b>解释：</b>第一个查询中，Alice 和 Bob 可以移动到建筑 2 ，因为 heights[0] &lt; heights[2] 且 heights[1] &lt; heights[2] 。\n",
    "第二个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[0] &lt; heights[5] 且 heights[3] &lt; heights[5] 。\n",
    "第三个查询中，Alice 无法与 Bob 相遇，因为 Alice 不能移动到任何其他建筑。\n",
    "第四个查询中，Alice 和 Bob 可以移动到建筑 5 ，因为 heights[3] &lt; heights[5] 且 heights[4] &lt; heights[5] 。\n",
    "第五个查询中，Alice 和 Bob 已经在同一栋建筑中。\n",
    "对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。\n",
    "对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>heights = [5,3,8,2,6,1,4,6], queries = [[0,7],[3,5],[5,2],[3,0],[1,6]]\n",
    "<b>输出：</b>[7,6,-1,4,6]\n",
    "<strong>解释：</strong>第一个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[0] &lt; heights[7] 。\n",
    "第二个查询中，Alice 和 Bob 可以移动到建筑 6 ，因为 heights[3] &lt; heights[6] 且 heights[5] &lt; heights[6] 。\n",
    "第三个查询中，Alice 无法与 Bob 相遇，因为 Bob 不能移动到任何其他建筑。\n",
    "第四个查询中，Alice 和 Bob 可以移动到建筑 4 ，因为 heights[3] &lt; heights[4] 且 heights[0] &lt; heights[4] 。\n",
    "第五个查询中，Alice 可以直接移动到 Bob 的建筑，因为 heights[1] &lt; heights[6] 。\n",
    "对于 ans[i] != -1 ，ans[i] 是 Alice 和 Bob 可以相遇的建筑中最左边建筑的下标。\n",
    "对于 ans[i] == -1 ，不存在 Alice 和 Bob 可以相遇的建筑。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= heights.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= heights[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>queries[i] = [a<sub>i</sub>, b<sub>i</sub>]</code></li>\n",
    "\t<li><code>0 &lt;= a<sub>i</sub>, b<sub>i</sub> &lt;= heights.length - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-building-where-alice-and-bob-can-meet](https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-building-where-alice-and-bob-can-meet](https://leetcode.cn/problems/find-building-where-alice-and-bob-can-meet/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[6,4,8,5,2,7]\\n[[0,1],[0,3],[2,4],[3,4],[2,2]]', '[5,3,8,2,6,1,4,6]\\n[[0,7],[3,5],[5,2],[3,0],[1,6]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, a: List[int], q: List[List[int]]) -> List[int]:\n",
    "        n = len(a)\n",
    "        m = len(q)\n",
    "        ans = [-1] * m\n",
    "        left = [[] for i in range(n)]\n",
    "        \n",
    "        for q_idx, (i, j) in enumerate(q):\n",
    "            if i > j:\n",
    "                i, j = j, i\n",
    "            if i == j or a[i] < a[j]:\n",
    "                ans[q_idx] = j\n",
    "            else:\n",
    "                left[j].append((i,q_idx))\n",
    "        \n",
    "        h = []\n",
    "        for i in range(n):\n",
    "            while h and h[0][0] < a[i]:\n",
    "                q_idx = heappop(h)[1]\n",
    "                ans[q_idx] = i\n",
    "            \n",
    "            for j,q_idx in left[i]:\n",
    "                heappush(h,(a[j],q_idx))\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        g={}\n",
    "        for i in range(len(queries)):\n",
    "\n",
    "            x = queries[i]\n",
    "            if x[0]>x[1]:x[0],x[1]=x[1],x[0]\n",
    "            if x[1] == x[0]:\n",
    "                queries[i] = x[0]\n",
    "            else:\n",
    "\n",
    "                if  heights[x[0]] < heights[x[1]]:\n",
    "                    queries[i] = x[1]\n",
    "\n",
    "                elif x[0] in g and x[1]>=g[x[0]][0] and x[1]<=g[x[0]][1]:\n",
    "                    queries[i] = g[x[0]][1]\n",
    "                    if g[x[0]][1]==len(heights):queries[i]=-1\n",
    "                else:\n",
    "                    y = max(x[0] , x[1])\n",
    "                    y1=max(heights[x[0]],heights[x[1]])\n",
    "                    if y1>=max(heights[y:]):\n",
    "                        queries[i]=-1\n",
    "                        g[x[0]]=[y,len(heights)]\n",
    "                    else:\n",
    "                        for j in range(y+1,len(heights)):\n",
    "                            if heights[j]>y1:\n",
    "                                queries[i]=j\n",
    "                                g[x[0]]=[y,j]\n",
    "                                break\n",
    "\n",
    "        return queries\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, h: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 查找 >= max(x, y)区间内，值 >= max(h[x], h[y])的最小下标\n",
    "        n = len(queries)\n",
    "        s = list(range(n))\n",
    "        s.sort(key = lambda x: max(queries[x]), reverse=True)\n",
    "        # print(s)\n",
    "        r = len(h) - 1\n",
    "        q = deque([])\n",
    "        # qi = deque([])\n",
    "        # qi = []\n",
    "        for i in s:\n",
    "            x, y = queries[i]\n",
    "            l = max(x, y)\n",
    "            while r >= 0 and r >= l:\n",
    "                # add r\n",
    "                while q and h[q[0]] <= h[r]:\n",
    "                    q.popleft()\n",
    "                    # qi.popleft()\n",
    "                q.appendleft(r)\n",
    "                # qi.appendleft(h[r])\n",
    "                r -= 1\n",
    "            v = max(h[x], h[y])\n",
    "            if x < l:\n",
    "                if h[x] < h[y]:\n",
    "                    queries[i] = y\n",
    "                    continue\n",
    "            if y < l:\n",
    "                if h[y] < h[x]:\n",
    "                    queries[i] = x\n",
    "                    continue\n",
    "            if x == y:\n",
    "                queries[i] = x\n",
    "                continue\n",
    "            v += 1\n",
    "            index = bisect_left(q, v, key = lambda x: h[x])\n",
    "            if index == len(q):\n",
    "                queries[i] = -1    \n",
    "            else:\n",
    "                queries[i] = q[index]\n",
    "        return queries\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        stack = []\n",
    "        info = [None] * len(heights)\n",
    "\n",
    "\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            while stack and heights[i] >= heights[stack[-1]]:\n",
    "                k = stack.pop()\n",
    "                info[k] = stack[-1] if stack else -1\n",
    "            \n",
    "            stack.append(i)\n",
    "        \n",
    "        while stack:\n",
    "            k = stack.pop()\n",
    "            info[k] = stack[-1] if stack else -1\n",
    "        \n",
    "        \n",
    "        # print(info)\n",
    "        res = [-1] * len(queries)\n",
    "\n",
    "        for i in range(len(queries)):\n",
    "            x, y = queries[i]\n",
    "            if x == y:\n",
    "                res[i] = x\n",
    "                continue\n",
    "\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            \n",
    "            if heights[x] < heights[y]:\n",
    "                res[i] = y\n",
    "            # elif info[x] != -1:\n",
    "            #     res[i] = info[x]\n",
    "            elif info[x] == -1: # 数组最大值\n",
    "                pass\n",
    "            else:\n",
    "                # info[x]\n",
    "                # while info[x] != -1 and heights[info[y]] < \n",
    "                while info[y] != -1 and heights[info[y]] <= heights[x]:\n",
    "                    y = info[y]\n",
    "                \n",
    "                if info[y] != -1:\n",
    "                    res[i] = info[y]\n",
    "        \n",
    "        return res\n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        m = len(queries)\n",
    "        rightmax = [-1] * n\n",
    "        ans = [-1] * m\n",
    "        stack = list()\n",
    "        for i in range(n):\n",
    "            while stack and heights[i] > heights[stack[-1]]:\n",
    "                rightmax[stack[-1]] = i \n",
    "                stack.pop()\n",
    "            stack.append(i)\n",
    "\n",
    "        # print(rightmax)\n",
    "\n",
    "        for idx, (i, j) in enumerate(queries):\n",
    "            if i == j:\n",
    "                ans[idx] = i\n",
    "                continue\n",
    "            \n",
    "            if i > j:\n",
    "                i, j = j, i\n",
    "\n",
    "            if heights[i] < heights[j]:\n",
    "                ans[idx] = j\n",
    "                continue\n",
    "\n",
    "            if rightmax[i] == -1 or rightmax[j] == -1:\n",
    "                continue\n",
    "\n",
    "            k = j\n",
    "            while rightmax[k] != -1:\n",
    "                k = rightmax[k]\n",
    "                if heights[k] > heights[i]:\n",
    "                    # print(idx, k, heights[i], heights[k])\n",
    "                    ans[idx] = k\n",
    "                    break\n",
    "            \n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        j = len(heights) - 1\n",
    "        st = []\n",
    "        for i in sorted(range(n), key = lambda x: -max(queries[x])):\n",
    "            a, b = queries[i]\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            if a == b or heights[b] > heights[a]:\n",
    "                ans[i] = b\n",
    "                continue\n",
    "            while j > b:\n",
    "                while st and heights[st[-1]] <= heights[j]:\n",
    "                    st.pop()\n",
    "                st.append(j)\n",
    "                j -= 1\n",
    "            \n",
    "            h = heights[a]\n",
    "            if not st or heights[st[0]] <= h:\n",
    "                continue\n",
    "            k = bisect.bisect_left(st, -h, key = lambda x:-heights[x])\n",
    "            ans[i] = st[k-1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        answer = [None] * len(queries)\n",
    "        qs = []\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a == b:\n",
    "                answer[i] = a\n",
    "            else:\n",
    "                a, b = min(a, b), max(a, b)\n",
    "                if heights[a] < heights[b]:\n",
    "                    answer[i] = b\n",
    "                else:\n",
    "                    qs.append((b, heights[a], i))\n",
    "        qs.sort()\n",
    "        stack = []\n",
    "        for i in range(len(heights) - 1, -1, -1):\n",
    "            h = heights[i]\n",
    "            while qs and qs[-1][0] == i:\n",
    "                b, h2, j = qs.pop()\n",
    "                k = bisect_left(stack, -h2, key=lambda x: -x[0])\n",
    "                if k > 0:\n",
    "                    answer[j] = stack[k - 1][1]\n",
    "                else:\n",
    "                    answer[j] = -1\n",
    "            while stack and stack[-1][0] <= h:\n",
    "                stack.pop()\n",
    "            stack.append((h, i))\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        mx = [0] * heights.__len__() * 4\n",
    "\n",
    "        def build(p, l, r):\n",
    "            if l==r:\n",
    "                mx[p] = heights[l]\n",
    "                return \n",
    "            mid = (l+r) //2 \n",
    "            \n",
    "            build(2*p+1, l, mid)\n",
    "            build(2*p+2, mid+1, r)\n",
    "            mx[p] = max(mx[2*p+1], mx[2*p+2])\n",
    "\n",
    "        def query(p, l, r, L, val):\n",
    "            \n",
    "            if L > r:\n",
    "                return -1\n",
    "            \n",
    "            if mx[p] > val:\n",
    "                if l == r:\n",
    "                    return l\n",
    "\n",
    "                mid = (l + r) // 2\n",
    "                if L <= mid:\n",
    "                    left = query(2*p+1, l, mid, L, val)\n",
    "                    if left != -1:\n",
    "                        return left \n",
    "                    else:\n",
    "                        return query(2*p+2, mid+1, r, L, val)\n",
    "                else:\n",
    "                    return query(2*p+2, mid+1, r, L, val)\n",
    "            else:\n",
    "                return -1\n",
    "\n",
    "        build(0, 0, heights.__len__()-1)\n",
    "        ans = []\n",
    "        for alice, bob in queries:\n",
    "            if alice > bob:\n",
    "                alice, bob = bob, alice\n",
    "            if alice == bob or heights[bob] > heights[alice]:\n",
    "                ans.append(bob)\n",
    "                continue\n",
    "            ans.append(query(0, 0, heights.__len__()-1, bob+1, max(heights[bob], heights[alice])))\n",
    "        return ans \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        mx = [0] * (n * 4)\n",
    "\n",
    "        def build(o, l, r):\n",
    "            if l == r:\n",
    "                mx[o] = heights[l - 1]\n",
    "                return\n",
    "            m = (l + r) // 2\n",
    "            build(o * 2, l, m)\n",
    "            build(o * 2 + 1, m + 1, r)\n",
    "            mx[o] = max(mx[o * 2], mx[o * 2 + 1])\n",
    "\n",
    "        def query(o, l, r, L, v):\n",
    "            if v >= mx[o]: return 0\n",
    "            if l == r: return l\n",
    "            m = (l + r) // 2\n",
    "            if L <= m: \n",
    "                pos = query(o * 2, l, m, L, v)\n",
    "                if pos > 0: return pos\n",
    "            return query(o * 2 + 1, m + 1, r, L, v)\n",
    "\n",
    "        build(1, 1, n)\n",
    "        ans = []\n",
    "        for i, j in queries:\n",
    "            if i > j:\n",
    "                i, j = j, i\n",
    "            if heights[i] < heights[j] or i == j:\n",
    "                ans.append(j)\n",
    "            else:\n",
    "                pos = query(1, 1, n, j + 1, heights[i])\n",
    "                ans.append(pos - 1)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n,m=len(heights),len(queries)\n",
    "        queries=sorted([(i,min(a,b),max(a,b)) for i,(a,b) in enumerate(queries)],key=lambda x:x[2],reverse=True)\n",
    "        print(queries)\n",
    "\n",
    "        j=n-1\n",
    "        res=[-1]*m\n",
    "        stack=[]\n",
    "        for i,a,b in queries:\n",
    "            if a==b:res[i]=b;continue\n",
    "            \n",
    "            maxv=max(heights[a],heights[b])\n",
    "            # 将当前序号后面的数构造成单调栈（单调递增）\n",
    "            while j>b:\n",
    "                while stack and heights[stack[-1]]<=heights[j]:\n",
    "                    stack.pop()\n",
    "                stack.append(j)\n",
    "                j-=1\n",
    "            # print(a,b,heights[a],heights[b],stack)\n",
    "            if heights[a]<heights[b]:res[i]=b;continue\n",
    "            if not stack:continue\n",
    "            # 二分查找合适位置\n",
    "            l,r=0,len(stack)-1\n",
    "            while l<r:\n",
    "                mid=l+r+1>>1\n",
    "                if heights[stack[mid]]<=maxv:\n",
    "                    r=mid-1\n",
    "                else:\n",
    "                    l=mid\n",
    "            \n",
    "            if heights[stack[r]]>maxv:\n",
    "                res[i]=stack[r]\n",
    "            \n",
    "            # print(a,b,res[i])\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        m = len(queries)\n",
    "        ans = [-1]*m\n",
    "        ind = list(range(m))\n",
    "        lst = [max(heights[x], heights[y]) for x, y in queries]\n",
    "        ind.sort(key=lambda it: -lst[it])\n",
    "        \n",
    "        index = list(range(n))\n",
    "        index.sort(key=lambda it: -heights[it])\n",
    "        j = 0\n",
    "        lst = SortedList()\n",
    "        for i in ind:\n",
    "            x, y = queries[i]\n",
    "            if x < y and heights[x] < heights[y]:\n",
    "                ans[i] = y\n",
    "                continue\n",
    "            if y < x and heights[y] < heights[x]:\n",
    "                ans[i] = x\n",
    "                continue\n",
    "            if x == y:\n",
    "                ans[i] = y\n",
    "                continue\n",
    "            c = max(heights[x], heights[y])\n",
    "            while j < n and heights[index[j]] > c:\n",
    "                lst.add(index[j])\n",
    "                j += 1\n",
    "            \n",
    "            k = lst.bisect_right(max(x, y))\n",
    "            if 0<=k<len(lst):\n",
    "                ans[i] = lst[k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, h: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(queries)\n",
    "        ans = [-1] * n\n",
    "        q = []\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if a > b:\n",
    "                a, b = b, a\n",
    "            if h[a] < h[b] or a == b:\n",
    "                ans[i] = b\n",
    "            else:\n",
    "                q.append((b, h[a], i))\n",
    "        \n",
    "        j = 0        \n",
    "        q.append((inf, inf, -1))\n",
    "        q.sort()        \n",
    "        hp = [(inf, inf)]\n",
    "        for i, a in enumerate(h):\n",
    "            while q[j][0] < i:\n",
    "                heappush(hp, (q[j][1], q[j][2]))\n",
    "                j += 1\n",
    "            while hp[0][0] < a:\n",
    "                ans[heappop(hp)[1]] = i            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [-1] * len(queries)\n",
    "        left = [[] for _ in heights]\n",
    "        for qi, (i, j) in enumerate(queries):\n",
    "            if i > j:\n",
    "                i, j = j, i  # 保证 i <= j\n",
    "            if i == j or heights[i] < heights[j]:\n",
    "                ans[qi] = j  # i 直接跳到 j\n",
    "            else:\n",
    "                left[j].append((heights[i], qi))  # 离线\n",
    "\n",
    "        h = []\n",
    "        for i, x in enumerate(heights):  # 从小到大枚举下标 i\n",
    "            while h and h[0][0] < x:\n",
    "                ans[heappop(h)[1]] = i  # 可以跳到 i（此时 i 是最小的）\n",
    "            for p in left[i]:\n",
    "                heappush(h, p)  # 后面再回答\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        ans = [-1] * len(queries)\n",
    "        queries_left = [[] for _ in range(n)]\n",
    "        for idx,(i,j) in enumerate(queries):\n",
    "            if i > j:\n",
    "                i,j = j,i\n",
    "            if i==j or heights[i] < heights[j]:\n",
    "                ans[idx] = j\n",
    "            else:\n",
    "                queries_left[j].append((heights[i],idx))\n",
    "        # \n",
    "        h = []\n",
    "        for j, qs in enumerate(queries_left):\n",
    "            while h and h[0][0] < heights[j]:\n",
    "                _,idx = heapq.heappop(h)\n",
    "                ans[idx] = j\n",
    "            for q in qs:\n",
    "                heapq.heappush(h, q)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        to_answer = [[] for _ in range(n)]\n",
    "        ans = [0] * len(queries)\n",
    "        for i, (u, v) in enumerate(queries):\n",
    "            if u > v: u, v = v, u\n",
    "            if u == v or heights[u] < heights[v]: ans[i] = v\n",
    "            else: to_answer[v].append((i, heights[u]))\n",
    "        stack = [(-1, inf)]\n",
    "        for idx in range(n-1, -1, -1):\n",
    "            while stack[-1][1] <= heights[idx]:\n",
    "                stack.pop()\n",
    "            for i, v in to_answer[idx]:\n",
    "                l, r = 0, len(stack) - 1\n",
    "                while l <= r:\n",
    "                    m = (l + r) // 2\n",
    "                    if stack[m][1] > v: l = m + 1\n",
    "                    else: r = m - 1\n",
    "                ans[i] = stack[r][0]\n",
    "            stack.append((idx, heights[idx]))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef leftmostBuildingQueries(self, heights, queries):\n",
    "\t\tn = len(queries)\n",
    "\t\tans = [-1] * n\n",
    "\t\tpool = []\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tl = min(queries[i])\n",
    "\t\t\tr = max(queries[i])\n",
    "\t\t\tif l == r or heights[l] < heights[r]:\n",
    "\t\t\t\tans[i] = r\n",
    "\t\t\telse:\n",
    "\t\t\t\tpool.append([l, r, i])\n",
    "\t\tpool.sort(key = lambda x: x[1])\n",
    "\t\tip = 0\n",
    "\t\tq = []\n",
    "\t\tfor i, h in enumerate(heights):\n",
    "\t\t\twhile ip < len(pool) and pool[ip][1] < i:\n",
    "\t\t\t\theapq.heappush(q, [heights[pool[ip][0]], pool[ip][2]])\n",
    "\t\t\t\tip += 1\n",
    "\t\t\twhile q and q[0][0] < h:\n",
    "\t\t\t\tans[q[0][1]] = i\n",
    "\t\t\t\theapq.heappop(q)\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, h: List[int], q: List[List[int]]) -> List[int]:\n",
    "        n = len(h)\n",
    "        m = len(q)\n",
    "        ans = [-1] * m\n",
    "        cand = [[] for _ in range(n)]\n",
    "        for i, (x, y) in enumerate(q):\n",
    "            if x < y:\n",
    "                x, y = y, x\n",
    "            cand[x].append((max(h[x], h[y]), i))\n",
    "\n",
    "        h = h + [inf]\n",
    "        stk = [n]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if len(cand[i]):\n",
    "                for y, ids in cand[i]:\n",
    "                    lo, hi = 0, len(stk) - 1\n",
    "                    while lo < hi:\n",
    "                        mid = (lo + hi + 1) // 2\n",
    "                        if h[stk[mid]] > y:\n",
    "                            lo = mid\n",
    "                        else:\n",
    "                            hi = mid - 1\n",
    "\n",
    "                    if h[stk[lo]] != inf:\n",
    "                        ans[ids] = stk[lo]\n",
    "\n",
    "            while stk and h[i] >= h[stk[-1]]:\n",
    "                stk.pop()\n",
    "            stk.append(i)\n",
    "\n",
    "        for i, [x, y] in enumerate(q):\n",
    "            if x == y:\n",
    "                ans[i] = x\n",
    "            if x > y:\n",
    "                x, y = y, x\n",
    "            if h[x] < h[y]:\n",
    "                ans[i] = y\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self,n):\n",
    "        self.F = [inf] * (n+1)\n",
    "        self.V = [inf] * n\n",
    "        self.n = n+1\n",
    "    \n",
    "    def update(self,pos,v):\n",
    "        self.V[pos] = v\n",
    "        pos += 1\n",
    "        while pos < self.n:\n",
    "            self.F[pos] = min(self.F[pos],v)\n",
    "            pos += pos & -pos\n",
    "    \n",
    "    def query(self,a,b):\n",
    "        if a == b:return self.V[a]\n",
    "        a += 1;b += 1\n",
    "        if b-(b&-b) >= a:\n",
    "            res = min(self.query(a-1,b-(b&-b)-1),self.F[b])\n",
    "        else:\n",
    "            res = min(self.query(a-1,b-2),self.V[b-1])\n",
    "        return res\n",
    "            \n",
    "            \n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        Q = [[min(a,b),max(a,b),idx] for idx,(a,b) in enumerate(queries)]\n",
    "        Q.sort(key = lambda x:x[1])\n",
    "        st = []\n",
    "        pos = len(heights)-1\n",
    "        Res = [-1] * len(queries)\n",
    "        S = sorted(set(heights))\n",
    "        D = {};l = len(S)\n",
    "        for idx,i in enumerate(S):\n",
    "            D[i] = idx\n",
    "        Tr = BIT(l)\n",
    "        for a,b,idx in Q[::-1]:\n",
    "            if a == b or heights[b] > heights[a]:Res[idx] = b;continue\n",
    "            while b < pos:\n",
    "                Tr.update(D[heights[pos]],pos)\n",
    "                pos -= 1\n",
    "            if D[heights[a]] == l-1:continue\n",
    "            Res[idx] = Tr.query(D[heights[a]]+1,l-1)\n",
    "            if Res[idx] == inf:Res[idx] = -1\n",
    "        return Res\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    \"\"\"\r\n",
    "        1. 離線 + Min Heap\r\n",
    "    \"\"\"\r\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\r\n",
    "        ans = [-1] * len(queries)\r\n",
    "        # 依照 j 來處理\r\n",
    "        left = defaultdict(list)\r\n",
    "        for q_idx, (i, j) in enumerate(queries):\r\n",
    "            # 保證 i <= j\r\n",
    "            if i > j:\r\n",
    "                i, j = j, i\r\n",
    "            \r\n",
    "            # 可以從 i 直接跳到 j ， 直接回答\r\n",
    "            if i == j or heights[i] < heights[j]:\r\n",
    "                ans[q_idx] = j\r\n",
    "            else:\r\n",
    "                left[j].append((heights[i], q_idx)) # 離線\r\n",
    "        hp = [] # min heap\r\n",
    "        for j, h_j in enumerate(heights):\r\n",
    "            # 若堆頂元素的高度 hp[0][0](h_i) < h_j ，可以跳到 j，即該詢問答案為 j\r\n",
    "            while hp and hp[0][0] < h_j:\r\n",
    "                q_idx = heappop(hp)[1]\r\n",
    "                ans[q_idx] = j # 回答\r\n",
    "            # 將 left[j] 中的詢問加入堆中\r\n",
    "            for p in left[j]:\r\n",
    "                heappush(hp, p)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import PriorityQueue\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        res = [-1 for _ in queries]\n",
    "        n = len(heights)\n",
    "        left = [ [] for _ in range(n) ]\n",
    "        for qindex, (ai, bi) in enumerate(queries):\n",
    "            if ai>bi:\n",
    "                ai, bi = bi, ai \n",
    "            if ai==bi or heights[ai]<heights[bi]:\n",
    "                res[qindex] = bi \n",
    "            else:\n",
    "                left[bi].append((heights[ai], qindex))\n",
    "        print(\"left: \", left)\n",
    "        pq = PriorityQueue()\n",
    "        for i, height in enumerate(heights):\n",
    "            # 先弹出\n",
    "            if i==5:\n",
    "                print(pq.queue, height)\n",
    "            while ( not pq.empty() ) and pq.queue[0][0]<height:\n",
    "                hai, qindex = pq.get()\n",
    "                res[qindex] = i \n",
    "            for hai, qindex in left[i]:\n",
    "                pq.put((hai, qindex))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        queries = [sorted(x) for x in queries]\n",
    "        n = len(heights)\n",
    "        m = len(queries)\n",
    "        ans = [-1] * m\n",
    "        dq = deque()  # [heights[i], i]  单调减的栈\n",
    "        pos = n - 1\n",
    "        for i, (idx, idy) in sorted(enumerate(queries), key=lambda x: max(x[1]), reverse=True):\n",
    "            if heights[idx] < heights[idy] or idx == idy:\n",
    "                ans[i] = idy\n",
    "                continue\n",
    "            while idy < pos:\n",
    "                while dq and dq[0][0] <= heights[pos]:\n",
    "                    dq.popleft()\n",
    "                dq.appendleft([heights[pos], pos])\n",
    "                pos -= 1\n",
    "            # print(stack)\n",
    "            p = bisect_left(dq, [heights[idx], n])\n",
    "            if p == len(dq):\n",
    "                ans[i] = -1\n",
    "            else:\n",
    "                ans[i] = dq[p][1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, h: List[int], query: List[List[int]]) -> List[int]:\n",
    "        n, m = len(h), len(query)\n",
    "        ans = [-1] * m\n",
    "        sz = 0\n",
    "        while (1 << sz) <= n: sz += 1\n",
    "        sz += 1\n",
    "        f = [[int(0) for j in range(sz)] for i in range(n + 2)]\n",
    "        for i in range(n) : f[i][0] = h[i]\n",
    "        for j in range(1, sz):\n",
    "            for i in range(n):\n",
    "                if i + (1 << j) - 1 >= n : break\n",
    "                f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1])\n",
    "        lg2 = [0] * (n + 2)\n",
    "        for i in range(2, n + 2): lg2[i] = lg2[i // 2] + 1\n",
    "        def getmax(l, r):\n",
    "            L = lg2[r - l + 1]\n",
    "            return max(f[l][L], f[r - (1 << L) + 1][L])\n",
    "        i = 0\n",
    "        for a, b in query:\n",
    "            if a > b: a, b = b, a\n",
    "            if a == b or h[a] < h[b]:\n",
    "                ans[i] = b\n",
    "                i += 1\n",
    "                continue\n",
    "            l = b\n",
    "            r = n - 1\n",
    "            mid = 0\n",
    "            while l < r:\n",
    "                mid = (l + r) // 2\n",
    "                if getmax(b, mid) > h[a]: r = mid \n",
    "                else : l = mid + 1\n",
    "            if getmax(b, l) > h[a] : ans[i] = l\n",
    "            i += 1\n",
    "        return ans\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #为每个建筑求能到的最左和最右\n",
    "        hash={}#记录b对应的a和index\n",
    "        for i in range(len(queries)):\n",
    "            a=min(queries[i])\n",
    "            b=max(queries[i])\n",
    "            if b not in hash:\n",
    "                hash[b]=[]\n",
    "            hash[b].append([a,i])\n",
    "        n=len(heights)    \n",
    "        #记录右边单调递增\n",
    "        st=[]\n",
    "        res=[-1]*len(queries)\n",
    "        for i in range(n-1,-1,-1):\n",
    "            h=heights[i]\n",
    "            while st and h>heights[st[-1]]:\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "            if i in hash:\n",
    "                n_st=st[::-1]\n",
    "                for a,index in hash[i]:\n",
    "                    b=i\n",
    "                    if a>b:\n",
    "                        a,b=b,a\n",
    "                    if heights[b]>heights[a] or a==b:\n",
    "                        res[index]=b\n",
    "                    else:\n",
    "                        l,r=0,len(n_st)-1\n",
    "                        while l<=r:\n",
    "                            mid=(l+r)//2\n",
    "                            if heights[n_st[mid]]>heights[a]:\n",
    "                                r=mid-1\n",
    "                            else:\n",
    "                                l=mid+1\n",
    "                        #print(r,n_st)\n",
    "                        if (r+1>=len(n_st)):\n",
    "                            res[index]=-1\n",
    "                        else:\n",
    "                            res[index]=n_st[r+1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "离线方法， 最小堆\n",
    "'''\n",
    "        \n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(heights)\n",
    "\n",
    "        end = collections.defaultdict(list)\n",
    "        ans = [-1] * len(queries)\n",
    "\n",
    "        \n",
    "\n",
    "        for i, (l, r) in enumerate(queries):\n",
    "            if l > r:\n",
    "                l, r = r, l   \n",
    "\n",
    "            if l == r:\n",
    "                ans[i] = l\n",
    "            elif heights[r] > heights[l]:\n",
    "                ans[i] = r\n",
    "            else:\n",
    "                end[r].append((l, i))\n",
    "\n",
    "        sort_r = sorted(end.keys())\n",
    "        handle = []\n",
    "\n",
    "        for tar in range(2, n):\n",
    "            for l, i in end[tar-1]:\n",
    "                heapq.heappush(handle, (heights[l], i))\n",
    "\n",
    "            while handle:\n",
    "                lh, i = handle[0]\n",
    "                if heights[tar] > lh:\n",
    "                    ans[i] = tar\n",
    "                    heapq.heappop(handle)\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return ans\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:    \n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(queries)  \n",
    "        hash={}#记录b对应的a和index\n",
    "        for i in range(n):\n",
    "            a=min(queries[i])\n",
    "            b=max(queries[i])\n",
    "            if b not in hash:\n",
    "                hash[b]=[]\n",
    "            hash[b].append([a,i])\n",
    "          \n",
    "        #记录右边单调递增\n",
    "        st=[]\n",
    "        res=[-1]*n\n",
    "        for i in range(len(heights)-1,-1,-1):\n",
    "            h=heights[i]\n",
    "            while st and h>heights[st[-1]]:\n",
    "                st.pop()\n",
    "            st.append(i)\n",
    "            if i in hash:\n",
    "                b=i\n",
    "                for a,index in hash[i]:\n",
    "                    if heights[b]>heights[a] or a==b:\n",
    "                        res[index]=b\n",
    "                    else:\n",
    "                        l,r=0,len(st)-1\n",
    "                        while l<=r:\n",
    "                            mid=(l+r)//2\n",
    "                            if heights[st[mid]]>heights[a]:\n",
    "                                l=mid+1\n",
    "                            else:\n",
    "                                r=mid-1\n",
    "                        #print(r,n_st)\n",
    "                        if (l-1<0):\n",
    "                            res[index]=-1\n",
    "                        else:\n",
    "                            res[index]=st[l-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        se = sorted(list(set(heights)))\n",
    "        dic = dict(zip(se, range(1, len(se)+1)))\n",
    "        n = len(heights)\n",
    "        # heights = sorted(range(n), key = lambda x: heights[x])\n",
    "        # heights = sorted(range(n), key = lambda x: heights[x])\n",
    "        # heights = [x + 1 for x in heights]\n",
    "        heights = [dic[x] for x in heights]\n",
    "        c = max(heights)\n",
    "        arr = [n] * (c+1)\n",
    "        arr[0] = 0\n",
    "        def insert(idx, x):\n",
    "            while x:\n",
    "                arr[x] = min(arr[x], idx)\n",
    "                x -= (-x) & x\n",
    "        \n",
    "        def get(x):\n",
    "            x = x+1\n",
    "            ans = n\n",
    "            while x <= c:\n",
    "                ans = min(arr[x], ans)\n",
    "                x += (-x) & x\n",
    "            return ans\n",
    "        \n",
    "        queries = [sorted(q) for q in queries]\n",
    "\n",
    "        s_q = sorted(queries, key = lambda x: x[1])[::-1]\n",
    "        idxs = sorted(range(len(queries)), key = lambda x: queries[x][1])[::-1]\n",
    "        dic = dict(zip(idxs, range(len(idxs))))\n",
    "        ans = []\n",
    "        p = n-1\n",
    "        for q in s_q:\n",
    "            while p > q[1]:\n",
    "                    insert(p, heights[p])\n",
    "                    p -= 1\n",
    "            if heights[q[0]] < heights[q[1]] or q[0] == q[1]:\n",
    "                ans.append(q[1])\n",
    "                continue\n",
    "            m = max(heights[q[0]], heights[q[1]])\n",
    "            app = get(m)\n",
    "            if app < n:\n",
    "                ans.append(app)\n",
    "            else:\n",
    "                ans.append(-1)\n",
    "\n",
    "        return [ans[dic[x]] for x in range(len(idxs))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import log2\n",
    "class SparseTable:\n",
    "    def __init__(self, nums: List[int], merge_func: Callable[List[int], int]) -> None:\n",
    "        # merge_func: max, min\n",
    "\n",
    "        n = len(nums)\n",
    "        k = int(log2(n)) + 1\n",
    "\n",
    "        self.merge_func = merge_func\n",
    "\n",
    "        # st[i][j]: 长度为 2^j 的子数组 nums[i, i + 2^j - 1] 上的最值\n",
    "        # 将长度为 2^j 的子数组 nums[i, i + 2^j - 1]\n",
    "        # 划分为两个长度为 2^(j -1) 的子数组：\n",
    "        # nums[i, i + 2^(j - 1) - 1],\n",
    "        # nums[i + 2^(j - 1), 2 ^ j - 1]\n",
    "        # 则有区间最值等于两个小区间最值的最值，即：\n",
    "        # max(nums[i, i + 2^j - 1]) = max(\n",
    "        #   max(nums[i, i + 2^(j - 1) - 1]),\n",
    "        #   max(nums[i + 2^(j - 1), 2^j - 1])\n",
    "        # )\n",
    "        # min(nums[i, i + 2^j - 1]) = min(\n",
    "        #   min(nums[i, i + 2^(j - 1) - 1]),\n",
    "        #   min(nums[i + 2^(j - 1), 2^j - 1])\n",
    "        # )\n",
    "        self.st = [[0] * k for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            self.st[i][0] = nums[i]\n",
    "\n",
    "        for j in range(1, k):\n",
    "            for i in range(n - (1 << j) + 1):\n",
    "                self.st[i][j] = self.merge_func(\n",
    "                    self.st[i][j - 1],\n",
    "                    self.st[i + (1 << (j - 1))][j - 1]\n",
    "                )\n",
    "\n",
    "    def query(self, left: int, right: int) -> int:\n",
    "        # 将区间 [left, right] 划分为两个长度为 2^k 的重叠区间：\n",
    "        # [left, left + 2^k - 1] 和 [right - 2^k + 1, right]\n",
    "        # 区间 [left, right] 上的最值，即为两个重叠区间上最值的最值，即：\n",
    "        # max(nums[left, right]) = max(\n",
    "        #   max(nums[left, left + 2^k - 1]),\n",
    "        #   max(nums[right - 2^k + 1, right])\n",
    "        # )\n",
    "        # min(nums[left, right]) = min(\n",
    "        #   min(nums[left, left + 2^k - 1]),\n",
    "        #   min(nums[right - 2^k + 1, right])\n",
    "        # )\n",
    "\n",
    "        k = int(log2(right - left + 1))\n",
    "        return self.merge_func(\n",
    "            self.st[left][k],\n",
    "            self.st[right - (1 << k) + 1][k]\n",
    "        )\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        d = defaultdict(list)\n",
    "        res = [-1] * len(queries)\n",
    "        for qi, (a, b) in enumerate(queries):\n",
    "            if a > b:\n",
    "                a, b = b, a \n",
    "            if a == b or heights[b] > heights[a]:\n",
    "                res[qi] = b \n",
    "            else:\n",
    "                d[heights[a]].append([2, b, qi]) #2代表查询操作\n",
    "        for i in range(n):\n",
    "            d[heights[i]].append([1, i]) #1代表插值操作\n",
    "\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList() #存下标\n",
    "\n",
    "        #从大到小插入值，找符合条件的最小下标\n",
    "        for k in sorted(d.keys(), reverse=True):\n",
    "            for q in d[k]:\n",
    "                if q[0] == 2: #查询\n",
    "                    if not sl or q[1] > sl[-1]: #找不到在b右侧的比heighs[a]大的下标\n",
    "                        continue\n",
    "                    else:\n",
    "                        res[q[2]] = sl[sl.bisect_left(q[1])]\n",
    "            for q in d[k]:\n",
    "                if q[0] == 1:\n",
    "                    sl.add(q[1]) #插入值为k的下标\n",
    "        return res\n",
    "\n",
    "\n",
    "        # n = len(heights)\n",
    "        # qs = [[] for _ in range(n)]\n",
    "        # res = [0] * len(queries)\n",
    "        # for i, (a, b) in enumerate(queries):\n",
    "        #     if a > b:\n",
    "        #         a, b = b, a\n",
    "        #     if a == b or heights[a] < heights[b]:\n",
    "        #         res[i] = b \n",
    "        #     else:\n",
    "        #         qs[b].append((i, heights[a]))\n",
    "        # stk = [(-1, inf)]\n",
    "        # for i in range(n - 1, -1, -1):\n",
    "        #     while stk[-1][1] <= heights[i]:\n",
    "        #         stk.pop()\n",
    "        #     #需要找最左侧的比当前更大的数字，但是在单调栈里是找最右侧的（最新加入的）\n",
    "        #     for qi, x in qs[i]:\n",
    "        #         left, right = 0, len(stk)\n",
    "        #         while left + 1 < right:\n",
    "        #             mid = (left + right) // 2\n",
    "        #             if stk[mid][1] > x:\n",
    "        #                 left = mid\n",
    "        #             else:\n",
    "        #                 right = mid\n",
    "        #         res[qi] = stk[left][0]\n",
    "        #     stk.append((i, heights[i]))\n",
    "        # return res\n",
    "\n",
    "        # st_max = SparseTable(heights, max)\n",
    "        # n, q = len(heights), len(queries)\n",
    "        # res = [-1] * q\n",
    "        # for i, (a, b) in enumerate(queries):\n",
    "        #     mx = max(heights[a], heights[b])\n",
    "        #     if a > b:\n",
    "        #         a, b = b, a\n",
    "        #     # if a == b or heights[b] > heights[a]:\n",
    "        #     #     res[i] = b \n",
    "        #     #     continue\n",
    "        #     # if st_max.query(b, n - 1) < mx:\n",
    "        #     #     continue\n",
    "        #     left, right = b, n\n",
    "        #     while left + 1 < right:\n",
    "        #         mid = (left + right) // 2\n",
    "        #         if st_max.query(left, mid) > mx:\n",
    "        #             right = mid\n",
    "        #         else:\n",
    "        #             left = mid\n",
    "        #     if right == n or heights[right] <= mx:\n",
    "        #         res[i] = -1\n",
    "        #     else:\n",
    "        #         res[i] = right\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        res = defaultdict(list)\n",
    "        ans = [-1]*len(queries)\n",
    "        for z,(i,j) in enumerate(queries):\n",
    "            if i > j: i,j = j,i\n",
    "            if heights[i] < heights[j] or i == j: ans[z] = j; continue\n",
    "            res[j].append([i, z])\n",
    "        h = []\n",
    "        for i,x in enumerate(heights):\n",
    "            for l,r in res[i]:\n",
    "                heappush(h, [heights[l], r])\n",
    "                # print(h, h[0][0], x)\n",
    "            while h and h[0][0] < x:  # \n",
    "                a,b = heappop(h)\n",
    "                ans[b] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start\n",
    "        self.end = end \n",
    "        self.left = None \n",
    "        self.right = None \n",
    "        self.curMax = 0\n",
    "\n",
    "class SegmentTree:\n",
    "    def __init__(self, array):\n",
    "        n = len(array)\n",
    "        self.array = array\n",
    "        self.root = self.build(0, n - 1)\n",
    "    \n",
    "    def build(self, start, end):\n",
    "        if start > end:\n",
    "            return \n",
    "        root = Node(start, end)\n",
    "        if start == end:\n",
    "            root.curMax = self.array[start]\n",
    "            return root\n",
    "        mid = start + (end - start) // 2 \n",
    "        root.left = self.build(start, mid)\n",
    "        root.right = self.build(mid + 1, end)\n",
    "        root.curMax = max(root.left.curMax, root.right.curMax)\n",
    "        return root \n",
    "    \n",
    "    def query(self, root, index, target):\n",
    "        if root.end < index:\n",
    "            return - 1\n",
    "        if root.curMax <= target:\n",
    "            return - 1\n",
    "        if root.start == root.end:\n",
    "            return root.start\n",
    "        mid = root.start + (root.end - root.start) // 2 \n",
    "        if index <= mid:\n",
    "            l = self.query(root.left, index, target)\n",
    "            if l != - 1:\n",
    "                return l \n",
    "        return self.query(root.right, index, target)\n",
    "    \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def leftmostBuildingQueries(self, heights: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(heights)\n",
    "        sg = SegmentTree(heights)\n",
    "        res = []\n",
    "        for i, j in queries:\n",
    "            if i > j:\n",
    "                i, j = j, i \n",
    "            if heights[j] > heights[i] or i == j:\n",
    "                res.append(j)\n",
    "                continue\n",
    "            if j == n - 1:\n",
    "                res.append(-1)\n",
    "                continue \n",
    "            idx = sg.query(sg.root, j + 1, heights[i])\n",
    "            res.append(idx)\n",
    "        return res "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
